#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod (int)(998244353)
int c, T;
int n, m;
vector<int>t[2005];
int dep[2005];
int getans1(){
    int mx = -1e18;
    for(int i = 1; i <= n; i++){
        for(auto TO : t[i]){
            for(int j = 1; j <= n; j++)dep[j] = 0;
            queue<int>q;
            q.emplace(i);
            dep[i] = 1;
            while(!q.empty()){
                int p = q.front();
                q.pop();
                for(auto to : t[p]){
                    if(to == TO && p == i)continue;
                    if(to == i && p == TO)continue;
                    if(!dep[to]){
                        dep[to] = dep[p] + 1;
                        q.emplace(to);
                    }
                }
            }
            if(dep[TO]){
                mx = max(mx, -m -dep[TO]+2);
            }
        }
    }
    return mx;
}
int f[10][10];
int baoli(int mb){
    int CNT = 0;
    for(int i = 0; i < (1<<n*(n-1)/2); i++){
        if(__builtin_popcount(i) != m - 1)continue;
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                f[j][k] = 1e9;
            }
        }
        for(int j = 1; j <= n; j++)f[j][j] = 0;
        int num = 0;
        for(int j = 1; j <= n; j++){
            for(int k = j + 1; k <= n; k++){
                if(i>>num&1){
                    f[j][k] = f[k][j] = 1;
                }
                num++;
            }
        }
        for(int k = 1; k <= n; k++){
            for(int x = 1; x <= n; x++){
                for(int y = 1; y <= n; y++){
                    f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
                }
            }
        }
        int ans = 0;
        for(int p = 1; p <= n; p++){
            for(auto to : t[p]){
                if(to > p){
                    ans -= f[p][to];
                }
            }
        }
        CNT += (ans==mb);
    }
    return CNT;
}
void clr(){
    for(int i = 1; i <= n; i++)t[i].clear();
}
int fac(int x){
    int ans = 1;
    for(int i = 1; i <= x; i++){
        ans = ans * i % mod;
    }
    return ans;
}
signed main(){
    freopen("oi.in", "r", stdin);
    freopen("oi.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> c >> T;
    int id = 0;
    while(T--){
        id++;
        cin >> n >> m;
        for(int i = 1; i <= m; i++){
            int x, y;
            cin >> x >> y;
            t[x].emplace_back(y);
            t[y].emplace_back(x);
        }
        if(c <= 2){
            cout << getans1() << " " << baoli(getans1()) << '\n';
        }else{
            cout << getans1() << " " << 0 << '\n';
        }
        clr();
    }
    return 0;
}